package leetcode.monotoni;

import java.util.Stack;

/**
 * 739. 每日温度
 * 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * 输入: temperatures = [73,74,75,71,69,72,76,73]
 * 输出: [1,1,4,2,1,1,0,0]
 * 示例 2:
 * <p>
 * 输入: temperatures = [30,40,50,60]
 * 输出: [1,1,1,0]
 * 示例 3:
 * <p>
 * 输入: temperatures = [30,60,90]
 * 输出: [1,1,0]
 */
public class DailyTemperatures {
    public int[] dailyTemperatures(int[] temperatures) {

        int[] ans = new int[temperatures.length];
        int n = temperatures.length;
        if (n == 0) {
            return ans;
        }

        Stack<int[]> stack = new Stack<>();

        for (int i = 0; i < n; i++) {
            int cur = temperatures[i];
            // [0]为 坐标 [1]为温度
            // 如果比栈里的大，处理一下栈里的，直到没有比当前值小的
            while (!stack.isEmpty() && cur > stack.peek()[1]) {
                int[] peek = stack.peek();
                ans[peek[0]] = i - peek[0];
                stack.pop();
            }
            // 栈一定是单调递减的
            stack.push(new int[]{i, cur});
        }

        return ans;
    }
}


